import java.util.*;

/**
 * @author LKQ
 * @date 2022/6/3 13:19
 * @description 排序 + 优先队列
 */
public class Solution {
    public static void main(String[] args) {

    }
    public int[] minInterval(int[][] intervals, int[] queries) {
        // 左端点升序排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int len = queries.length;
        // 记录排序前每个查询的位置，方便后面填写
        int[][] qu = new int[len][2];
        for (int i = 0; i < len; i++) {
            qu[i][0] = queries[i];
            qu[i][1] = i;
        }
        // 查询数组升序排序
        Arrays.sort(qu, (a, b) -> a[0] - b[0]);
        int[] ans = new int[len];
        Arrays.fill(ans, -1);
        // 最小堆，维护区间长度升序排序
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> (a[1] - a[0]) - (b[1] - b[0]));
        int index = 0;
        for (int i = 0; i < len; i++) {
            // 将所有起始位置小于查询位置的区间加入优先队列
            while (index < intervals.length && qu[i][0] >= intervals[index][0]) {
                queue.add(new int[]{intervals[index][0], intervals[index][1]});
                index++;
            }
            // 队列中右端点如果小于查询值，直接删除，因为后面更大的用不上
            while (!queue.isEmpty() && queue.peek()[1] < qu[i][0]) {
                queue.poll();
            }
            if (!queue.isEmpty()) {
                int[] t = queue.peek();
                ans[qu[i][1]] = t[1] - t[0] + 1;
            }
        }
        return ans;
    }
}
